#pragma once
#include<iostream>
using namespace std;
//写一个循环链表
template <typename T>
class chainnode 
{
public:
	T data;
	chainnode<T>* next;

	//构造
	chainnode(T value):data(value),next(nullptr){}
};

template<typename T>
class circchain {
private:
	chainnode<T>* head;
	chainnode<T>* tail;
	int size;
	
public:
	circchain():head(nullptr),size(0){}
	~circchain() { clear(); }
	//while(size>0) {delete(0);}

	//添加节点
	void insert(T value) {
		chainnode<T>* newnode = new chainnode<T>(value);
		if (head == nullptr) {
			head = newnode;
			head->next = head;
			tail = head;
		}
		else {
			tail->next = newnode;
			tail = newnode;//更新尾指针
			newnode->next = head;//循环
		}
		size++;
	}

	//删除节点并返回其值
	T remove(int position) {
		if (size == 0 || position < 0 || position >= size) {
			throw std::out_of_range("Invalid position");//抛出异常 超出范围类型
		}
		chainnode<T>* todelete;
		T value;
			if (size == 1)
			{
				todelete = head;
				value = todelete->data;
				head = nullptr;//更新头指针
				tail = head;
			}
			else {
			//找到要删除的节点的前一个结点，断开
			chainnode<T>* prev = head;
			for (int i = 0; i < (position - 1 + size) % size; i++) 
			//考虑到了position=0的情况
			{
				prev = prev->next;
			}
			todelete = prev->next;
			value = todelete->data;

			//如果要删除头指针
			if (todelete == head) {
				head = head->next;
			}
			prev->next = todelete->next;
			
		}
		delete todelete;
		size--;
		return value;
	}

	//获取当前链表大小
	int getSize()const {
		return size;
	}

	//获取当前元素（只剩下一个元素时使用）
	T getValue() {
		if (size == 1 && head != nullptr) {
			return head->data;
		}
		throw std::runtime_error("No current element or multiple elements");
	}

	//清空链表
	void clear() {
		while (size > 0) {
			remove(0);
		}
	}
};